package edu.xidian.onlinedocument.utils.ot.internal;

import edu.xidian.onlinedocument.utils.ot.internal.operations.*;

import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;

/**
 * OT算法核心算法
 * 这里默认后端在transform(A,B)中，A是先来的操作，B是后来的操作
 * 最终目的是让text.apply(A).apply(transform(A,B)) = text.apply(B).apply(transform(B,A))
 */
public class Transform {
    private Transform() {}

    // 所有transform的总出口方法
    public static Result transform(ChangesList changesA, ChangesList changesB) {
        ResultBuilder resultBuilder = new ResultBuilder(changesA.getChanges(), changesB.getChanges());
        Change leftChange = null;
        Change rightChange = null;
        while (resultBuilder.hasNext()) {
            leftChange = resultBuilder.left();
            rightChange = resultBuilder.right();
            // A: Retain, B: Retain / Insert/ Delete
            if (ChangeType.isRetain(leftChange)) {
                if (ChangeType.isRetain(rightChange)) {
                    transform((Retain) leftChange, (Retain) rightChange, resultBuilder);
                }
                else if (ChangeType.isInsert(rightChange)) {
                    transform((Retain) leftChange, (Insert) rightChange, resultBuilder);
                }
                else if (ChangeType.isDelete(rightChange)) {
                    transform((Retain) leftChange, (Delete) rightChange, resultBuilder);
                }
            }
            // A: Insert, B: Retain / Insert/ Delete
            else if (ChangeType.isInsert(leftChange)) {
                if (ChangeType.isInsert(rightChange)) {
                    transform((Insert) leftChange, (Insert) rightChange, resultBuilder);
                }
                else if (ChangeType.isRetain(rightChange)) {
                    // 注意，这里不能重用transform(Retain,Insert)方法
                    transform((Insert) leftChange, (Retain) rightChange, resultBuilder);
                }
                else if (ChangeType.isDelete(rightChange)) {
                    transform((Insert) leftChange, (Delete) rightChange, resultBuilder);
                }
            }
            // A: Delete, B: Retain / Insert/ Delete
            else if (ChangeType.isDelete(leftChange)) {
                if (ChangeType.isDelete(rightChange)) {
                    transform((Delete) leftChange, (Delete) rightChange, resultBuilder);
                }
                else if (ChangeType.isRetain(rightChange)) {
                    // 注意，这里不能重用transform(Retain,Delete)方法
                    transform((Delete) leftChange, (Retain) rightChange, resultBuilder);
                }
                else if (ChangeType.isInsert(rightChange)) {
                    // 注意，这里不能重用transform(Insert,Delete)方法
                    transform((Delete) leftChange, (Insert) rightChange, resultBuilder);
                }
            }
        }
        return resultBuilder.build();
    }

    // A: Retain(n1), B: Retain(n2)时，
    // 如果n1 = n2，即接下来的操作是同一位置，则不做处理，两边都跳过
    // 如果n1 > n2，即接下来的操作位置中A的pos大于B的pos，因此先处理B的接下来操作，将坐标定位到B的retain值，并且使A的原始retain值减去相应值，并使指针往回退，以便之后执行完B的操作后继续A的操作
    // 如果n1 < n2，即接下来的操作位置中A的pos小于B的pos，因此先处理A的接下来操作，将坐标定位到A的retain值，并且使B的原始retain值减去相应值，并使指针往回退
    // 之所以可以修改builder的值，是因为函数参数中的builder同时也是取出retainA和retainB的builder，因此可以通过调用previous()使取A操作时保持原位不动
    // *************************
    // 例如 A: retain(5),insert("aa") ; B : retain(2),insert("b")。即 A: xxxxxaax, B: xxbxxxx
    // 在经过下述transform之后会变成 A: retain(3),insert("aa") ; B: retain(2),insert("b")
    // 并且下次执行left()和right()时取值分别为 A=Retain{length=3}, b=Insert{content="b"}，即A仍指向retain，B已经指向下一位insert
    // *************************
    private static void transform(Retain retainA, Retain retainB, ResultBuilder builder) {
        int min = 0;
        if (retainA.offset().equals(retainB.offset())) {
            min = retainA.offset();
        } else if (retainA.offset() > retainB.offset()) {
            min = retainB.offset();
            builder.replaceLeft(new Retain(retainA.offset() - retainB.offset()));
        } else if (retainA.offset() < retainB.offset()) {
            min = retainA.offset();
            builder.replaceRight(new Retain(retainB.offset() - retainA.offset()));
        }
        builder.addLeft(new Retain(min));
        builder.addRight(new Retain(min));
    }

    // A先retain，B先insert意味着在transform(Retain,Retain)中，A的retain位置要大于B的retain位置
    // 因此B的insert操作会影响A的retain，而A的后续操作不会影响到B，因此要将B的insert的影响反应到A上，B的insert直接加入
    // 注意这里的retainA.offset()，这里应当是已经作用过replaceLeft，即在这里retainA其实表示的是A的原始pos和B的原始pos的距离，
    // 并且已经在A'中加入了B的原始距离，因此这里加上insertB的字符串长度，刚好是B的insert作用完之后，A重定位的retain位置
    // *************************
    // 例如 A: retain(5),insert("aa") ; B : retain(2),insert("b")。即 A: xxxxxaax, B: xxbxxxx
    // 在经过上述transform之后会变成 A: retain(3),insert("aa") ; B: retain(2),insert("b")。有 A': retain(2) ; B':retain(2)
    // 第二次transform执行以下的方法，得到 A': retain(2),retain(4) ; B': retain(2),insert("b")
    // 最后把A剩余操作加入A'，得到 A': retain(2),retain(4),insert("aa") ; B': retain(2),insert("b")。得到AB'=BA': xxbxxxaax
    // *************************
    private static void transform(Retain retainA, Insert insertB, ResultBuilder builder) {
        builder.addLeft(new Retain(retainA.offset() + insertB.offset()));
        builder.addRight(insertB);
    }

    private static void transform(Insert insertA, Retain retainB, ResultBuilder builder) {
        builder.addLeft(insertA);
        builder.addRight(new Retain(retainB.offset() + insertA.offset()));
    }

    // A先retain，B先delete意味着在transform(Retain,Retain)中，A的retain位置要大于B的retain位置
    // 因此B的delete操作会影响A的retain之后的操作，而A的后续操作不会影响到B
    // 注意，delete操作是从retain的位置向后删除，insert操作也一样，是从retain位置向后增加
    // retainA.offset() == deleteB.offset()，意味着A执行完B的delete后位置，直接将B的delete加入B'
    // retainA.offset() > deleteB.offset()，意味着A执行完B的delete后还有剩余，则将A的retain改为剩余值，并加入B的delete到B'
    // retainA.offset() < deleteB.offset()，意味着A的当前长度不够B的delete去删除，因此加入一个delete值刚好为A的retain值的进入B'，而通过修改B的delete值来记录剩余值
    // *************************
    // 例如 A: retain(5),insert("aa") ; B: retain(2),delete(3)。即 A: xxxxxaa↓x, B: xx↓x
    // 执行一次transform后为 A: retain(3),insert("aa") ; B: retain(2),delete(3)
    // 执行第二次transform的方法即为下述方法，得到 A': retain(2) ; B': retain(2),delete(3)。
    // 最终结果为 A': retain(2),insert("aa") ; B': retain(2),delete(3)。即 AB'=BA': xxaax
    // *************************
    // 例如 A: retain(5),insert("aa") ; B: retain(2),delete(2)。即 A: xxxxxaa↓x, B: xx↓xx
    // 执行一次transform后为 A: retain(3),insert("aa") ; B: retain(2),delete(2)。有 A': retain(2) ; B': retain(2)
    // 执行第二次transform的方法即为下述方法，得到 A: retain(1),insert("aa")，B不变。有 A': retain(2) ; B': retain(2),delete(2)
    // 最后将A剩余的retain(1),insert("aa")加入到A'
    // 最终结果为 A': retain(2),retain(1),insert("aa") ; B': retain(2),delete(2)。即 AB'=BA': xxxaax
    // *************************
    private static void transform(Retain retainA, Delete deleteB, ResultBuilder builder) {
        if (retainA.offset().equals(deleteB.offset())) {
            builder.addRight(deleteB);
        } else if (retainA.offset() > deleteB.offset()) {
            builder.replaceLeft(new Retain(retainA.offset() - deleteB.offset()));
            builder.addRight(deleteB);
        } else if (retainA.offset() < deleteB.offset()) {
            builder.addRight(new Delete(retainA.offset()));
            builder.replaceRight(new Delete(deleteB.offset() - retainA.offset()));
        }
    }

    private static void transform(Delete deleteA, Retain retainB, ResultBuilder builder) {
        if (retainB.offset().equals(deleteA.offset())) {
            builder.addLeft(deleteA);
        } else if (retainB.offset() > deleteA.offset()) {
            builder.replaceRight(new Retain(retainB.offset() - deleteA.offset()));
            builder.addLeft(deleteA);
        } else if (retainB.offset() < deleteA.offset()) {
            builder.addLeft(new Delete(retainB.offset()));
            builder.replaceLeft(new Delete(deleteA.offset() - retainB.offset()));
        }
    }

    // 根据以上transform(Retain,Retain)和transform(Retain,Insert)方法的注释，可以知道只有当A、B的retain值相同或都为空时才会执行下述方法
    // 这里规定A操作优先于B操作，因此A'先加上A的insert字符串，再跳过B的insert字符串，而B'反过来是先跳过A的insert字符串，再加上B的insert字符串
    // 最后还需要统一 AB'=BA' 过程之后的retain值，或者说指针位置相同
    // *************************
    // 例如 A: retain(2),insert("aa"); B: retain(2),insert("b")。即 A: xxaaxxxx, B: xxbxxxx
    // 产生的最终结果为 A': retain(2),insert("aa"),retain(1); B': retain(2),retain(2),insert("b")。即AB'=BA': xxaabxxxx
    // *************************
    private static void transform(Insert insertA, Insert insertB, ResultBuilder builder) {
        //if (insertA.revision() <= insertB.revision()) {

            // A先insert，因为虽然在客户端上看B已经先insert了，但是实际上是A先，所以客户端也应该在B的insert的字符串前作用A的insert
            builder.addLeft(insertA);
            // 然后是A的retain，注意insert作用在text上时会修改其pos
            // 相当于加入了一个retain(A.length)，因此这里再retain(B.length)就能到两次insert的字符串的末尾
            builder.addLeft(new Retain(insertB.offset()));
            // B先retain，这是因为A已经先insert了，但B不知道，B的insert仍然是A未insert前的操作，因此要将A的insert的影响加上
            builder.addRight(new Retain(insertA.offset()));
            // 然后是B的insert，注意此时AB'后的retain位置是在B的insert字符串末尾
            builder.addRight(insertB);
        /*
        } else {
            builder.addLeft(new Retain(insertB.offset()));
            builder.addLeft(insertA);
            builder.addRight(insertB);
            builder.addRight(new Retain(insertA.offset()));
        }*/
    }

    // 首先，会执行到该方法说明A的insert和B的delete一定是基于同一个retain，或者说文本的同一个位置
    // 从服务器的角度来看，是A先基于该位置insert，然后B再基于该位置+A的insert字符串长度再delete
    // 由于那么A的insert就直接作用于B，即将A的insert直接加入A'
    // 而B的delete要在retain(A.length)之后再执行，因为B不知道A已经insert了，发的是没有"aa"情况下的retain，但A确实已经insert了，要加上影响
    // *************************
    // 例如 A: retain(3),insert("aa") ; B: retain(3),delete(2)，即 A: xxxaa↓xxx, B: xxx↓x
    // 执行下述方法后得 A': retain(3),insert("aa"), B': retain(3),retain(2),delete(2)，即 AB'=BA': xxxaax
    // *************************
    private static void transform(Insert insertA, Delete deleteB, ResultBuilder builder) {
        builder.addLeft(insertA);
        builder.addRight(new Retain(insertA.offset()));
        // 注意，这里和源代码不同，源代码是builder.addRight(deleteB)，这里之所以这样修改是因为A有可能是连续insert，这时候delete就会出问题
        // 因此将delete保留，直到A的insert结束
        builder.replaceRight(deleteB);
    }

    private static void transform(Delete deleteA, Insert insertB, ResultBuilder builder) {
        builder.addRight(insertB);
        builder.addLeft(new Retain(insertB.offset()));
        // 注意，这里和源代码不同，理由同上
        builder.replaceLeft(deleteA);
        //builder.addLeft(deleteA);
    }

    // 首先，会执行到该方法说明A的delete和B的delete一定是基于同一个retain，或者说文本的同一个位置
    // 从服务器角度来看，只需要比较谁delete的长度比较长，然后将多delete的客户端反映给少delete的客户端即可
    // deleteA.offset() == deleteB.offset()，意味着两边其实做了一样的操作，不用任何的处理
    // deleteA.offset() > deleteB.offset()，意味着A的delete长度要比B的delete长度要长，所以将多delete的部分记录到A'中发给B
    // deleteA.offset() < deleteB.offset()，意味着A的delete长度要比B的delete长度要短，所以将多delete的部分记录到B'中发给A
    // *************************
    // 例如 A: retain(3),delete(1) ; B: retain(3),delete(3)，即 A: xxx↓xx, B: xxx↓
    // 执行下述方法后得 A: retain(3),delete(1) ; B:retain(3),delete(2)。 有 A': retain(3) ; B': retain(3)
    // 将剩余部分放入B'，得到 A': retain(3) ; B': retain(3),delete(2)。即 AB'=BA': xxx
    // *************************
    private static void transform(Delete deleteA, Delete deleteB, ResultBuilder builder) {
        if (deleteA.offset() > deleteB.offset()) {
            builder.replaceLeft(new Delete(deleteA.offset() - deleteB.offset()));
        }
        else if (deleteA.offset() < deleteB.offset()) {
            builder.replaceRight(new Delete(deleteB.offset() - deleteA.offset()));
        }
    }

    // transform结果类
    public static class Result {
        private final ChangesList leftChanges;
        private final ChangesList rightChanges;

        public Result(List<Change> left, List<Change> right) {
            this.leftChanges = new ChangesList(left);
            this.rightChanges = new ChangesList(right);
        }

        public ChangesList getLeft() {
            return Merge.merge(leftChanges);
        }

        public ChangesList getRight() {
            return Merge.merge(rightChanges);
        }

        public void setLeftRevision(int revision) {
            leftChanges.setRevision(revision);
        }

        public void setRightRevision(int revision) {
            rightChanges.setRevision(revision);
        }
    }

    // Result的构造类，通过其build()方法来产生最后的Result结果，不接受Transform类以外的调用
    private static class ResultBuilder {
        private ListIterator<Change> leftIterator;
        private ListIterator<Change> rightIterator;
        private List<Change> leftResult;
        private List<Change> rightResult;
        boolean flipped = false;

        public ResultBuilder(List<Change> left, List<Change> right) {
            this.leftIterator = new ArrayList<>(left).listIterator();
            this.rightIterator = new ArrayList<>(right).listIterator();
            this.leftResult = new ArrayList<>(left.size());
            this.rightResult = new ArrayList<>(right.size());
        }

        boolean hasNext() {
            return leftIterator.hasNext() && rightIterator.hasNext();
        }

        boolean hasLeftNext() {
            return leftIterator.hasNext();
        }

        boolean hasRightNext() {
            return rightIterator.hasNext();
        }

        Change left() {
            return leftIterator.next();
        }

        Change right() {
            return rightIterator.next();
        }

        void addLeft(Change c) {
            leftResult.add(c);
        }

        void addRight(Change c) {
            rightResult.add(c);
        }

        // 注意，在set()之后调用了previous()，意味着下次执行next()，即addLeft()或addRight()，还是从旧位置开始
        void replaceLeft(Change c) {
            leftIterator.set(c);
            leftIterator.previous();
        }

        void replaceRight(Change c) {
            rightIterator.set(c);
            rightIterator.previous();
        }

        ResultBuilder flip() {
            flipped = !flipped;

            // 交换左右Changes
            List<Change> b = this.leftResult;
            this.leftResult = this.rightResult;
            this.rightResult = b;

            ListIterator<Change> i = this.leftIterator;
            this.leftIterator = this.rightIterator;
            this.rightIterator = i;

            return this;
        }

        public Result build() {
            // 将剩余的操作放入列表
            while (leftIterator.hasNext()) {
                leftResult.add(leftIterator.next());
            }
            while (rightIterator.hasNext()) {
                rightResult.add(rightIterator.next());
            }

            // 为了统一，这里规定由A得到的就是A'，B得到的就是B'
            // 因此出来的结果Result(A',B') 有text.apply(A).apply(B') = text.apply(B).apply(A')
            return flipped ? new Result(rightResult, leftResult) : new Result(leftResult, rightResult);
        }
    }
}
